package com.henry.base.interview;

//评测题目:
//有2个栈A和B，其中A里面有N个乱序元素，B是空栈。
//写一个算法把A的元素移动到B里面，并且排好序。
//空间要求：额外至多使用3个元素空间或变量。

//新建一个栈C
//类似汉诺塔递归算法实现
//A不是有序

import org.junit.Test;

import java.util.Stack;

public class StackTest190216 {
    @Test
    public void run() {
        Stack<Integer> a = new Stack<>();
        a.push(3);
        a.push(2);
        a.push(8);
        a.push(5);

        Stack<Integer> b = new Stack<>();
        deal1(a, b);

        System.out.println(b);

    }

    public void deal1(Stack<Integer> a, Stack<Integer> b) {
        if (a == null || a.isEmpty()) {
            return;
        }
        if (a.size() == 1) {
            b.push(a.pop());
            return;
        }
        Stack<Integer> c = new Stack<>();
        int max = a.pop();
        //找出A中最大的
        //压入栈B保存起来
        //剩下其余的元素压入C
        //然后让A指向C  继续操作

        int curr = 0;
        while (!a.isEmpty()) {
            curr = a.pop();

            if (curr < max) {
                c.push(curr);
            } else {
                c.push(max);
                max = curr;
            }
            if (a.isEmpty()) {
                b.push(max);
                a = c;
                c = new Stack<>();
                max = a.pop();
            }
        }
        b.push(curr);

    }
}






